#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

typedef struct {
    int n;                        // 图中顶点的数量
    int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
} Graph;

// 初始化图
void initGraph(Graph *g, int numVertices) {
    g->n = numVertices;
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            g->adjMatrix[i][j] = 0; // 初始化邻接矩阵，没有边为0
        }
    }
}

// 添加边
void addEdge(Graph *g, int u, int v) {
    g->adjMatrix[u][v] = 1;
    g->adjMatrix[v][u] = 1; // 因为是无向图，所以是对称的
}

// 全局数组，用于跟踪访问过的顶点
int visited[MAX_VERTICES];

// 深度优先搜索
void DFS(Graph *g, int v) {
    visited[v] = 1; // 标记当前顶点为已访问
    printf("Visited %d\n", v);

    for (int i = 0; i < g->n; i++) {
        if (g->adjMatrix[v][i] == 1 && !visited[i]) {
            DFS(g, i); // 对未访问的邻接顶点递归调用DFS
        }
    }
}

// 初始化访问标记数组
void initializeVisited(Graph *g) {
    for (int i = 0; i < g->n; i++) {
        visited[i] = 0;
    }
}

int main() {
    Graph g;
    initGraph(&g, 4); // 初始化一个有4个顶点的图
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 2);
    addEdge(&g, 2, 3);

    initializeVisited(&g);
    printf("Starting DFS from vertex 0:\n");
    DFS(&g, 0);
    /*
    连通图：在连通图中，从任何顶点开始DFS都将访问到图中的所有顶点。
    非连通图：在非连通图中，从一个顶点开始的DFS可能只访问到该顶点所在连通分量的顶点。如果你需要访问图中所有顶点，可能需要从多个顶点启动DFS，
    特别是需要分别从每个连通分量的至少一个顶点开始。
    */
    return 0;
}
